package twosum;

import java.util.HashMap;
import java.util.Map;

/**
 * @author LT
 */
public class twoSum {

    public static void main(String[] args) {
//        int[] ints = twoSum(new int[]{0, 3, 4, 0}, 0);
//        int[] ints = twoSum2(new int[]{0, 3, 4, 0}, 0);
        int[] ints = twoSum3(new int[]{0, 3, 4, 0}, 0);
    }

    /**
     * 暴力解题 时间复杂度O(n²)
     * <p>
     * 时间复杂度: 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)O(n
     * <p>
     * 空间复杂度：O(1)
     */
    private static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int i1 = 0; i1 < nums.length; i1++) {
                if (i == i1) {
                    continue;
                }
                if (nums[i] + nums[i1] == target) {
                    return new int[]{i, i1};
                }
            }
        }
        return null;
    }

    /**
     * 通过以空间换取速度的方式
     * 时间复杂度: O(n) 我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)
     * 空间复杂度: O(n) 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。
     */
    private static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int j = target - nums[i];
            Integer h = map.get(j);
            if (map.containsKey(j) && i != h) {
                return new int[]{i, h};
            }
        }
        throw new IllegalArgumentException("没有两数之和");
    }

    private static int[] twoSum3(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int j = target - nums[i];
            if (map.containsKey(j)) {
                return new int[]{map.get(j), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("没有两数之和");
    }


}
